from typing import List


class Solution:
    @staticmethod
    def findLE(arr, tar):
        lo = 0
        hi = len(arr) - 1
        while lo <= hi:
            mid = (lo + hi) >> 1
            if arr[mid] <= tar:
                lo = mid + 1
            else:
                hi = mid - 1
        return lo - 1

    def numSubseq(self, nums: List[int], target: int) -> int:
        # 记录每一个下标对应的最远再累加
        ans = 0
        n = len(nums)
        nums.sort()
        for i in range(n):
            t = Solution.findLE(nums, target - nums[i])
            if t < i: continue
            cnt = (1 << (t - i)) - 1  # 取i的情况下
            if 2 * nums[i] <= target:
                cnt += 1
            ans += cnt
            ans %= int(1e9 + 7)
        return ans


if __name__ == '__main__':
    s = Solution()
    r = s.numSubseq(nums=[3, 5, 6, 7], target=9)
    print(r)
